Announcements¶

Quiz 1 has been graded, and your results are posted on Gradescope

  • If you received a grade of 2 or less, or didn't attend yesterday's quiz: please respond to the Piazza poll about your availability to take Make-up Quiz 1, which will be next Monday 2/12 in discussion section.
  • If you received a grade of 3: you must submit a written explanation of how to improve any questions that you missed or where we left a comment for improvement. This response is due on Gradescope by Monday 2/12 at 12:05pm (i.e., the make-up quiz time).
  • If you received a grade of 4 or 5: congratulations! You earned a Pass or High Pass score toward your final course grade.

This week's assignments

  • Read NBFMG Sections 2.3-2.5 and Chapter 3 and complete the reading assessment 3 by Thursday 2/8
  • Programming assignment 3 is also released, due on Thursday 2/15 (along with Programming assignment 4)

Lecture 6: Proof of Work Mining¶

A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending.

– Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System

Learning Outcomes¶

By the end of today's lecture, you will learn:

  • The critical role that miners play to ensure agreement on the blockchain, meaning that everyone's view is essentially the same (except for very recent events).
  • Three types of attacks that a malicious could perform, and how Bitcoin is designed to prevent or disincentivize them.
  • The importance of an "honest majority" assumption, which means that the Bitcoin participants do need to trust that enough of the miners perform their role correctly, but do not need to trust any single one of them (and therefore, any single miner is easily replaceable).

Recap from last time¶

Bitcoin was invented in 2009 by an anonymous party (or parties) holding the pseudonym Satoshi Nakamato.

Bitcoin is a digital currency that does not require a single, trusted banking authority to manage everybody's transactions and bank balances. Instead, everyone on the Internet that uses the Bitcoin software collectively keeps track of how many Bitcoins each party holds at any moment in time.

In the physical world, when Bob receives a check from Alice, he may be suspicious that Alice is trying to deceive him. He needs to be able to verify the following three properties.

  1. Alice properly signed the check
  2. Alice possesses $1 in her bank account
  3. Alice does not double spend the money by writing a check to someone else at the same time

For a digital monetary system: digital signatures satisfy property #1, and a blockchain can satisfy the other two objectives.

A blockchain is a public ledger. It is:

  • Public, meaning that anyone can read it at any time.
  • Append-only, meaning that
    • Anyone can add new information at the end of the ledger, but
    • Nothing that is already in the ledger can ever be erased or overwritten.

19th century ledger

Source: Wikipedia

There are three types of data structures to consider within Bitcoin:

  • A transaction is a request to transfer money, just like a physical check from a sender to a receiver. The sender must sign the transaction to prove to the world that it consents to the money transfer, and the sender must point to the prior transaction(s) in which she received the money that she is trying to send now. Also, transactions are irrevocable.

    Sequence of transactions

  • Transactions are grouped into blocks. Each block contains several transactions (say, a few thousand). In Bitcoin, one block is created approximately every 10 minutes; we will discuss today how long it takes to create a block.

bitcoin blocks

[Source: mempool.space, at block 828285]

  • Finally, the blocks are linked together into a blockchain. Every block references the hash of the previous block in the chain (except for the first block, called the genesis block).

[Image source: Nakamoto whitepaper]

There are three types of participants within Bitcoin.

  • A light client only needs to hold one or more secret keys for a digital signature scheme.

  • A node additionally stores the entire state of the blockchain.

  • A miner additionally tries to write new blocks on the blockchain. (We will discuss miners in more detail today.)

Bitcoin needs miners; without them no new blocks would be created. So the Bitcoin system incentivizes people to create new blocks by providing two financial rewards:

  1. You get to create new coins out of thin air. Specifically, you get 6.25 Bitcoins, which is worth about $260,000 at current exchange rates. (This is the only way that new Bitcoins get introduced into circulation. In Bitcoin terminology, this is called a coinbase transaction.)

  2. You receive the transaction fees that people set aside for you within their transactions. The average Bitcoin transaction fee is currently around $6.50 per transaction.

The creation (or non-creation) of blocks needs to be done in such a way as to protect against 3 types of attacks.

  • Censorship: The miner can refuse to post certain transactions. This would break our goal of allowing anyone to append new information to the end of the book.

  • Inconsistency: The miner can send different states of the blockchain to different nodes. This would break our goal of having a global ledger that anyone can read.

  • Double spending: The miner could go back in time and rewrite an earlier block. This would break our goal that the ledger is append-only. Consider the following example:

    • An adversarial buyer Mallory creates a transaction to pay Alice, and puts this transaction into a block that she sends only to Alice.
    • At the same time, Mallory creates another block that sends her money to Bob. She broadcasts this block to the rest of the world.

[Image source: Bitcoin wiki]

6.1 Bitcoin ensures consistency, not speed¶

Mining a block earns you a lot of money! Seems like it might be nice to have the job of being a miner.

Question. Suppose that you have a job opening and there are millions of applicants. You can't hire everyone, and in fact you cannot even interview everyone. What would you do?

In fact, mining might be too nice of a job. If mining a block wins so much money, what's to stop the next person from overwriting the block so they get the mining rewards instead?

Modern computers are incredibly fast. They can transmit, write, and overwrite data in the blink of an eye.

But in a financial system like Bitcoin, speed is not the most important goal. Instead, we want to make sure that everyone has a consistent view of the blockchain ledger that they agree upon.

Cryptocurrencies like Bitcoin have been carefully designed to ensure that censorship, inconsistency, and double spending attacks are practically infeasible to perform.

(Note: Bitcoin's protections against these 3 attacks are actually related, but for the purposes of this class, we will treat them separately.)

Within Bitcoin, "practically infeasible" does not always mean "energy of the sun" levels of difficult. Instead, the goal is to ensure that the attacks are onerous enough to perform that:

  • It's very computationally expensive to try, and
  • Any rational attacker Mallory is incentivized to use that computing power instead to make money as a legitimate miner.

Question. How would you design a financial payment system to protect against censorship, inconsistency, and double-spending?

One possible option is to find a single person who the whole world trusts, and ask that person to be the sole miner in the scheme.

Sadly, we do not have such fully-trusted people. If we somehow found such a person, we might ask them to run everything for us, not just the banks. In political terms, this corresponds to a (benevolent?) dictatorship.

To extend the political analogy further, over the centuries humankind has designed democratic social structures in which we:

  • Impose limits on the power of any single actor, even the ones who seek power, and
  • Use elections to decide who gets to have temporary and limited power.

These political systems are often less efficient and nimble than a dictatorship might be, but they are more stable as a result.

Cryptocurrencies abide by these principles too! Let's see how.

6.2 Censorship Resistance via Leader Election¶

Let's see how Bitcoin thwarts these attacks, one at a time. For now, let's just assume that the miners all promise never to conduct a double-spend attack. (We'll fix this trust issue later.)

Bitcoin includes two components to thwart censorship:

  • There is a connected network of Bitcoin nodes that gossip or broadcast any transaction they hear. This way, any sender can get their transactions heard by any node and miner who happen to be connected to the network right now.

    We will say more about broadcast protocols in future lectures. For now let's assume that this part works perfectly. To see how it works, take a look at the animation at time 1:51 to 2:02 in the YouTube video below.

Out[3]:
  • There is a randomized election system (or in other words, a lottery) to choose the next miner. It doesn't matter (much) who wins the election; the important part is that the nodes have agreement on who has won.

    The upshot here is: each individual miner can still censor your transaction if they want. Nevertheless, as long as at least one miner is honest, then your transaction will eventually get put into a block.

    This is an example of an anytrust assumption; we will see more examples later in the semester.

The miner inserts into the newly-created block their winning lottery ticket -- which is formally called a nonce, for reasons we will see soon.

Other miners and nodes will only consider a block to be valid if it includes a winning nonce.

Just like with the earlier political analogy: we have designed a cryptocurrency that is more stable, but at the expense of speed. Whereas you might assume that an Internet-based money scheme would be fast, instead this system is purposely slow. Within Bitcoin,

  • A new miner is elected approximately once every 10 minutes. (More precisely, the time to the next winner is determined by a Poisson random variable.)
  • Each miner can create a block that is about 2 megabytes in size. Each block can hold a few thousand transactions.

In computer science terms: the throughput of this monetary system is low.

6.3 Consistency via Block Heights¶

This strategy also solves the problem of inconsistency, which was the fear that nodes might see different blockchains.

(Recall that we are assuming for the moment that miners will never go back and try to rewrite history.)

Even with this simplifying assumption in place, one concern is that two miners might win the lottery at (almost) the same time. If this happens

  • They will produce different blocks, called B and B2 in the picture below. These blocks might have the same transactions or they may have different transactions. Either way, they contain different nonces, and each block creator has awarded all mining rewards and fees to themselves.

  • But: both blocks will point to the same previous block, called A in the picture below.

In Bitcoin terminology, this is called a fork of the blockchain.

[Image source: Mango Research]

We can overcome this forking issue by using the peer-to-peer network to broadcast these blocks as well. Then we can impose a rule that all honest nodes should follow:

Always choose the largest* blockchain. As a tiebreaker, choose the chain that you heard first.

In Bitcoin terminology, each block contains a counter called its block height.

(*Note: we will make one small tweak to this rule in a few minutes.)

[Image source: Mango Research]

Once again, we have resolved an attack at the expense of speed. Let's look at the above picture in the following scenario: block A already exists, and then two miners win the lottery at nearly the same time and post blocks B and B2.

Suppose also your transaction occurred in block B but not in block B2.

  • Since a temporary fork has occurred, you cannot yet be sure that the whole network will coalesce around the block containing your transaction.
  • You will need to wait a few minutes to see which block "wins" by being extended first through another randomized election. (That could potentially have its own fork, but it's unlikely that too many of them will occur in a row.)

In computer science terms: the latency of any individual transaction is high.

6.4 Preventing Double Spends via Proof of Work¶

The final -- and most insidious -- attack that we have to prevent is the double spend.

The threat here is that a malicious buyer Mallory does the following.

  1. Create a block in which she gives her coins to seller Alice.
  2. Then create a new chain that is two blocks long in which she gives her coins to seller Bob. According to the rule we imposed previously, the whole world will switch to this new chain, so Alice no longer gets paid.

[Image source: Bitcoin wiki]

We will also solve this problem by intentionally imposing friction into the cryptocurrency. Specifically, we haven't discussed yet how miners win the election and get the right to create a new block.

Assume that there are more honest miners than dishonest miners. Our goal is to choose an election method that is fairly likely to elect an honest miner.

[Image source: Nakamoto whitepaper]

Here's how it works. Every miner collects all of the transactions from the peer-to-peer network, and forms a block. Then:

  1. The miner chooses the nonce value however it wants. (It can choose this at random, or make a counter, or anything it wants.)
  2. It runs the SHA-256 cryptographic hash over the block contents and the nonce.
  3. If the resulting hash digest starts with sufficiently many 0 bits, then the miner has won the election and quickly posts the result to the peer-to-peer network. Otherwise, it goes back to step #1 to try again.

Note that in each calculation of the hash function, the transactions in the block can remain the same (or they can change, if new transactions arrive and the miner wishes to add them to the block).

What's important is that the nonce changes for each execution of the hash function. The Bitcoin miners keep calculating

$$y = \texttt{SHA-256}(\texttt{block}, \texttt{nonce})$$

for many, many different nonces. The miner wins the election if this hash digest $y$ is a small enough number, i.e., it begins with enough 0 bits.

Currently, the Bitcoin miners collectively perform about $556 \cdot 10^{18}$ hashes per second.

This corresponds to $334 \cdot 10^{21}$ hashes every 10 minutes. The difficulty level of Bitcoin is currently set to require this many hash computations in expectation, in order to produce a winning nonce.

[Image source: blockchain.info]

This effort by the miners is called a proof of work. Only after performing this work can a miner post a block.

This is a lot of computational work! By means of comparison,

  • Your laptop's computer processor can probably perform about 100 million hashes per second.
  • If you have a nice video graphics card, it might be able to perform a few billion hashes per second.

So you would need around 100 billion graphics cards to keep up with the hash rate of the entire Bitcoin network!

Note: actual Bitcoin miners do not use general-purpose computer processors and graphics cards. Instead, they use special hardware that is designed solely to perform SHA-256 as quickly and cheaply as possible.

6.5 Puzzle Friendliness¶

To see the proof of work property in action, let's look at a recent block created on the Bitcoin blockchain.

In [8]:
# Every block references the hash of the previous block
# Fetching block 828285 that we explored last time
import requests
from binascii import unhexlify


# getting the block hash of block 828285
block_hash = requests.get('https://mempool.space/api/block-height/828285').text

# get block metadata
response = requests.get('https://mempool.space/api/block/' + block_hash)

block_hash = response.json()['previousblockhash']
print(block_hash)
000000000000000000021cc74c4da673f53f0cad485844e4bcdd4e42514ba420

The block hash starts with a lot of 0 hex characters! (19 of them, to be precise.) This is very unlikely to occur by chance.

Let's look at the hash digest in binary format.

In [22]:
print(format(int(block_hash, 16), '#0258b')[2:])
0000000000000000000000000000000000000000000000000000000000000000000000000000001000011100110001110100110001001101101001100111001111110101001111110000110010101101010010000101100001000100111001001011110011011101010011100100001001010001010010111010010000100000

This 256 bit string begins with 78 zeroes!

Question. If you choose a bitstring $x$ at random and feed it into SHA-256, what is the probability that the resulting output begins with 78 zeroes?

We can reason about this question using the random oracle property of a hash function, which states that the output "looks random."

If an adversary [Mallory] has not explicitly queried ... on some point $x$, then the value of $H(x)$ is completely random... at least as far as [Mallory] is concerned.

– Jon Katz and Yehuda Lindell, Introduction to Modern Cryptography

If every bit of the hash digest "looks" uniformly random, then this question is essentially asking about the chance of flipping a coin and it landing heads 78 times in a row.

The probability of this happening is $\frac{1}{2^{78}}$. You will need to attempt this experiment about $2^{78}$ times in order to find a hash digest like this one.

That is the proof of work game in action!

Concretely: Bitcoin relies on the following property of a hash function called puzzle friendliness.

Definition (puzzle friendliness). If we ask the miners to find an input $x$ whose SHA-256 hash digest $H(x)$ begins with $d$ zero bits in a row, then we believe there is no strategy that the miners can perform that is more effective than a guess-and-check approach. As a result, this computation is expected to take $2^d$ time.

Puzzle friendliness is a stronger guarantee than collision resistance, but a weaker guarantee than the random oracle assumption.

We have four different assumptions that we can make about a hash function:

Preimage resistance   <   Collision resistance   <   Puzzle friendliness   <   Random oracle.

Cryptographers assume that the SHA-2 and SHA-3 family of hash functions satisfy all of these assumptions.

Difficulty level adjustments¶

Because the computational power in the world goes up over time due to Moore's Law, the difficulty of the puzzle must adjust over time.

In Bitcoin, the difficulty changes once every 2 weeks or so.

  • If miners are finding blocks faster than every 10 minutes (on average), then the difficulty of finding a block increases. For example: the miners might be tasked to find hash digests that start with even more 0s.
  • If miners are finding blocks too slowly (on average), then the difficulty of finding a block decreases.

As a result, we need to make a small change to the rule that honest nodes follow:

Always choose the blockchain with the most cumulative difficulty.

In general, this typically corresponds to the blockchain with the tallest height.

6.6 An honest majority assumption¶

Bitcoin relies on the following assumption:

The majority of the computational power used for mining (at any given time) is controlled by honest miners.

If this assumption holds, then a leader election based on proof of work (eventually) stops double-spending attacks. That's because a dishonest miner cannot keep up with the raw computing power of the honest majority.

On the other hand: if an attacker actually has the majority of the hash power, then they can solve proof of work puzzles faster than the honest miners and can therefore rewrite history!

Note that this assumption is different than the "anytrust" assumption, which was all that we needed to ensure censorship resistance.

To see why Bitcoin needs an honest majority of computing power, let's use the same forking picture as before, but change the scenario as follows:

  • The time in the present is actually after block D has been posted.
  • A dishonest miner wants to revoke a transaction that occurred in the past, in block B.

[Image source: Mango Research]

To do this, the miner will need to post many proofs of work in a row, very quickly. It needs to create $3 + N$ blocks faster than the real world produces $N$ blocks.

This is a Markov chain problem!

Nakamoto's whitepaper includes the following function (which I translated from C++ into Python). It calculates the probability that an attacker who controls a q fraction of the computing power of the network can execute a double-spend attack to overwrite the last z blocks in the blockchain.

In [46]:
# Code adapted from the Bitcoin whitepaper at https://bitcoin.org/bitcoin.pdf

from math import exp, pow

def AttackerSuccessProbability(q: float, z: int):
    p = 1.0 - q
    poisson_lambda = z * (q / p)
    sum = 1.0
    for k in range(z+1):
        poisson = exp(-poisson_lambda)
        for i in range(1, k+1):
            poisson = poisson * poisson_lambda / i
        sum = sum - poisson * (1 - pow(q / p, z - k))
    return sum

q = 0.1
print("q =", q)
for z in range(10):
    print("z =", z, "\t  Prob =", format(AttackerSuccessProbability(q, z),"1.7f"))
print("")
q = 0.3
for z in range(0, 55, 5):
    print("z =", z, "\t  Prob =", format(AttackerSuccessProbability(q, z),"1.7f"))
q = 0.1
z = 0 	  Prob = 1.0000000
z = 1 	  Prob = 0.2045873
z = 2 	  Prob = 0.0509779
z = 3 	  Prob = 0.0131722
z = 4 	  Prob = 0.0034552
z = 5 	  Prob = 0.0009137
z = 6 	  Prob = 0.0002428
z = 7 	  Prob = 0.0000647
z = 8 	  Prob = 0.0000173
z = 9 	  Prob = 0.0000046

z = 0 	  Prob = 1.0000000
z = 5 	  Prob = 0.1773523
z = 10 	  Prob = 0.0416605
z = 15 	  Prob = 0.0101008
z = 20 	  Prob = 0.0024804
z = 25 	  Prob = 0.0006132
z = 30 	  Prob = 0.0001522
z = 35 	  Prob = 0.0000379
z = 40 	  Prob = 0.0000095
z = 45 	  Prob = 0.0000024
z = 50 	  Prob = 0.0000006

This code shows that even if a dishonest miner controls 10% of all the hash computing power on the blockchain, it will only have about a 1.3% chance of succeeding at double-spending a transaction from z = 3 blocks ago.

The attacker can increase its chance of success by buying or renting more computational power.

In response, defenders can resist this attack by waiting for more blocks to be confirmed in the public, honest chain.

Suppose there is a transaction that pays you money, but you don't trust the sender and you want to be confident that the money is "safe" and cannot be taken away from you through a double spend attack. You want to be 99.9% confident that your money is safe (i.e., that a double-spend succeeds with at most 0.1% probability).

The Nakamoto whitepaper includes the following table that shows how many blocks you need to see mined after your block, as a function of the dishonest miner's computational power.

Adversary's computational power # blocks required
10% 5
15% 8
20% 11
25% 15
30% 24
35% 41
40% 89
45% 340

There are two important takeaways from this table:

  1. The hash power required to execute a double-spend attack quickly becomes onerous enough to be not worth it, for all but the most expensive transactions. Even if the attacker controls even 10% of the Bitcoin network's computing power, executing a double spend attack will likely take more than one hour. By contrast, if the miner uses this hash power honestly to create new blocks, it could have earned (in expectation) tens of thousands of dollars in mining fees.

  2. On the other hand, if the attacker controls the majority of the hash power, then your money is never safe; even transactions made years ago could eventually be double-spent. This is called a 51% attack.

Summary¶

Let's state that a node considers a block to be finalized if it is at least $k$ blocks deep inside of the longest chain. We'll declare a transaction to be finalized if it is part of a finalized block. (The choice of $k$ here affects the probability of an erroneous decision.)

Overall, this proof of work construction achieves the following objectives.

  1. Liveness: Every transaction is eventually finalized by all honest nodes.
  2. Safety: Honest nodes do not finalize different blocks at the same height.

(Note that we have not yet provided any security guarantees to the light clients.)

In order to achieve these goals, Bitcoin is purposely designed to be:

  • Slow, in that transactions take awhile to become finalized.
  • Bounded, in that only a small number of transactions can be inserted in each block.
  • Computationally intensive, in order to distinguish the honest majority from the dishonest minority.

Over the next few weeks of this course, we will explore alternative ways to satisfy the liveness and safety goals with different tradeoffs.